\section{Arbre Binaire}

\begin{figure}
  \center
   \includegraphics[scale=0.5]{arbrebinaire}
  \caption{Exemple d'arbre binaire}
\end{figure}

L'arbre binaire est un concept de structure de données manipulant une hiérarchie de noeuds dont le premier est appelé racine. C'est une spécialisation de l'arbre n-aire.
La spécificité de ce type d'arbre est que chaque noeud peut avoir 0, 1 ou 2 fils mais pas plus.
Il n'y a pas de notion de tri dans le concept général qu'est l'arbre binaire.

Trois opérations principales sont définies dans le concept d'arbre binaire. Soit l'ajout, la suppression, et la recherche d'une valeur voir un itérateur.

Des opérations supplémentaires peuvent être implémentées et utilisées tel que « récupérer le fils gauche », « récupérer le fils droit » ou encore « récupérer la racine » si besoin est.

\subsection{Valeurs représentées par un noeud :}

Généralement, les noeuds des arbres contiennent des entiers. Mais ce n'est pas une règle. Un arbre doit donc pouvoir gérer n'importe quel type de valeurs. La seule obligation étant que les types de valeurs doivent avoir un outil de comparaison de l'égalité notamment pour la recherche de valeurs dans l'arbre (pas besoin de comparaison inférieur et supérieur car il n'y a pas de tri pour ce type d'arbre).

Pour gérer cette possibilité, le container Arbre Binaire doit être paramétré par le type de valeur mais également par un comparateur de ce type :

\begin{verbatim}
template<class T,class Comparateur>
class ArbreBinaire
\end{verbatim}

Où T peut être n'importe quel type et Comparateur est un comparateur du type T.

\subsection{Structures de stockage utilisables pour représenter un arbre binaire : }

Pour implémenter un arbre binaire, plusieurs structures peuvent être utilisées. Il y a deux structures particulièrement efficaces :

La première est un tableau dynamique. Pour représenter l'arborescence de l'arbre avec un tableau il est nécessaire de définir un comportement d'utilisation du tableau. Un comportement possible est celui-ci : Pour chaque noeud dans une case d'index i du tableau, les cases suivantes i+1 et i+2 sont réservé aux fils potentiels du noeud. Ce comportement est particulièrement efficace pour les arbre binaires complets (chaque noeud à deux fils) car il n'y a pas de cases du tableau non utilisées et donc de mémoire inutilisée. L'inconvénient d'utiliser des tableaux dynamiques est le coût dû au resize du tableau quand il est plein ou éventuellement quand il est très peut rempli.

Le deuxième moyen pour représenter un arbre binaire est l'utilisation de pointeurs. Chaque noeud contient deux pointeurs, un pour chaque fils. Dans ce cas, l'arbre dans son ensemble est représenté par le noeud racine à partir duquel on peut accéder à tous les autres noeuds. L'avantage de cette représentation des données de l'arbre est que la mémoire n'est pas gaspillé si l'arbre n'est pas complet et il n'y as pas de coût de resize.

Il serait intéressant pour un utilisateur du container ArbreBinaire de pouvoir choisir la structure qui stocke les noeuds. En effet si l'utilisateur sait que l'arbre qu'il va manipuler à tendance à ne pas être complet pour la plupart des noeuds et que la mémoire est limitée alors c'est mieux de choisir une implémentation utilisant des pointeur. 
Au contraire si il sait que sont arbre est complet alors l'utilisateur utilisera le tableau.

Pour se faire, l'arbre binaire doit contenir les deux implémentations voir d'autres encore et doit être paramétré par un entier par exemple qui représente pour la valeur 0, le tableau dynamique et pour la valeur 1, les pointeurs. Grâce à la spécialisation du template, il sera possible de faire deux implémentations utilisants chacune une structure différente.

\begin{verbatim}
template<int typeImplementation>
class ArbreBinaire
\end{verbatim}

Le template final de la classe ArbreBinaire fusionnera le template nécessaire pour choisir la structure de stockage des noeud et le template nécessaire pour pouvoir mettre n'importe quel type comme valeur dans un noeud. Il sera donc : 

\begin{verbatim}
template<class T,class Comparateur, int typeImplementation>
class ArbreBinaire
\end{verbatim}

\subsection{Le tas binaire : }

C'est une structure qui reprend le concept, l'architecture de l'arbre binaire et qui y ajoute des spécificités. C'est donc une spécialisation de l'arbre binaire.

\begin{itemize}
\renewcommand{\labelitemi}{$\triangleright$}
\item Tout d'abord, le tas binaire doit toujours vérifier la propriété d'arbre binaire complet. C'est-à-dire que seul le noeud le plus profond et à droite du tas peut ne pas être rempli entièrement.
\item De plus, le tas binaire dois être ordonné. C'est à dire que tous les fils d'un noeud père (2 maximum)  doivent avoir leur clé inférieur à celle du noeud père.
\end{itemize}

De la même manière que l'arbre binaire, le tas binaire peut contenir des clé de n'importe quel type. Il peut de plus utiliser différentes structures de stockage comme la liste dynamique ou les pointeurs.

Ce type d'arbre nécessite un comparateur de supériorité d'une clé par rapport à une autre ou d'infériorité en plus de l'égalité dont l'arbre binaire à besoin pour la recherche de part sa spécificité d'être ordonner.

Le template pour la classe TasBinaire est donc le même que pour l'ArbreBinaire soit :

\begin{verbatim}
template<class T,class Comparateur, int typeImplementation>
class TasBinaire
\end{verbatim}

Les méthodes d'ajout et de suppression doivent être redéfinies par rapport à l'arbre binaire car il faut garder le tas ordonné. L'itérateur reste le même.

\subsection{Arbre binaire de recherche : }

L'arbre binaire de recherche est également une spécification de l'arbre binaire et reprend donc sa structure.

Sa spécificité est que chaque noeud contient une clé tel que celle-ci est supérieur à la clé du noeud du fils gauche et inférieur à la clé du noeud du fils droit.

De même que le tas binaire, ses clés peuvent être de n'importe quel type et donc un comparateur doit être fournit pour tester l'égalité et la supériorité ou infériorité.

Il peut également être implémenter avec différentes structure de stockage (liste, pointeur).

Ses méthodes d'ajout et de suppression doivent également être redéfinies de part la spécificité propre de l'arbre binaire de recherche.

Son template est donc le même que pour l'arbre binaire : 

\begin{verbatim}
template<class T,class Comparateur, int typeImplementation>
class ArbreBinaireDeRecherche
\end{verbatim}

L'algorithme de recherche peut être redéfinis d'une manière plus efficace avec la recherche dichotomique rendu possible par la spécificité de ce type d'arbre.

\subsection{Arbre rouge et noir :}

\begin{figure}
  \center
   \includegraphics[scale=0.5]{arbrerougeetnoir}
  \caption{Exemple d'arbre rouge et noir}
\end{figure}

L'arbre rouge et noir est une spécialisation de l'arbre binaire de recherche. Il utilise donc la même structures avec des informations en plus sur chaque noeud qui est sa couleur.

Il rajoute les règles suivantes : 

\begin{itemize}
\renewcommand{\labelitemi}{$\triangleright$}
\item Un noeud est soit rouge soit noir. 
\item La racine est noire. 
\item Le parent d'un noeud rouge est noir.
\item Le chemin de chaque feuille à la racine contient le même nombre de noeuds noirs. 
\end{itemize}

L'arbre rouge et noir peut avoir des clés de n'importe quel type et peux être implémenté avec différentes structures de stockage de mêmes que les arbres binaires. De plus ses noeuds respectent la même règle d'ordre que l'arbre binaire de recherche et doit donc utiliser un comparateur similaire. Son template est donc :

\begin{verbatim}
template<class T,class Comparateur, int typeImplementation>
class ArbreRougeEtNoir
\end{verbatim}

L'insertion et la suppression doit être redéfinie de par la spécificité de l'arbre rouge et noir qui utilise des couleurs.

\subsection{L'arbre AVL :}

\begin{figure}
  \center
   \includegraphics[scale=0.5]{arbreAVL}
  \caption{Exemple d'arbre AVL}
\end{figure}

L'arbre AVL est également une spécialisation de l'arbre binaire de recherche.
Sa spécificité est la suivante : les hauteurs des deux sous-arbres d'un même noeud diffèrent au plus de un.

Sa structure est la même que l'arbre binaire de recherche. La différence se trouve dans les méthodes d'insertion et de suppression où des rotation sur les sous-arbres déséquilibrés sont effectué.

Le template est donc le même que celui de l'arbre binaire de recherche : 

\begin{verbatim}
template<class T,class Comparateur, int typeImplementation>
class ArbreAVL
\end{verbatim}
   
